package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 813. 最大平均值和的分组
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/30 14:43
 */
public class LargestSumOfAverages {

    public static void main(String[] args) {
        LargestSumOfAverages test = new LargestSumOfAverages();

        // 20
        int[] arr = {9, 1, 2, 3, 9};
        int k = 3;

        // 20.50000
//        int[] arr = {1, 2, 3, 4, 5, 6, 7};
//        int k = 4;

        double v = test.largestSumOfAverages(arr, k);
        System.out.println(v);
    }

    public double largestSumOfAverages(int[] nums, int k) {
        int length = nums.length;
        double[][] arr = new double[length][k];
        k--;
        double sum = 0;
        for (int i = 0; i < length; i++) {
            sum += nums[i];
            arr[i][0] = sum / (i + 1);
        }
        for (int i = 1; i < length; i++) {
            int end = Math.min(k, i);
            for (int j = 1; j <= end; j++) {
                sum = 0D;
                arr[i][j] = arr[i - 1][j - 1] + sum;
                for (int t = 1; t <= i - j + 1; t++) {
                    sum += nums[i - t + 1];
                    arr[i][j] = Math.max(arr[i][j], arr[i - t][j - 1] + sum / t);
                }
            }
        }
        return arr[length - 1][k];
    }

}
